'''
https://leetcode.cn/problems/house-robber-iii/description/
'''
from typing import Optional

from c06_tree.utils import TreeNode


class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        # 模拟尝试，超时了
        def process(cur, flag):
            if not cur: return 0
            # 当前不偷
            ans = process(cur.left, True) + process(cur.right, True)
            if flag:
                # 如果当前可以偷
                ans2 = cur.val + process(cur.left, False) + process(cur.right, False)
                ans = max(ans, ans2)
            return ans

        return process(root, True)
    def rob2(self, root: Optional[TreeNode]) -> int:
        # 记忆化搜索
        dp = {}
        def process(cur, flag):
            if not cur: return 0
            if (cur, flag) in dp: return dp[(cur, flag)]
            # 当前不偷
            ans = process(cur.left, True) + process(cur.right, True)
            if flag:
                # 如果当前可以偷
                ans2 = cur.val + process(cur.left, False) + process(cur.right, False)
                ans = max(ans, ans2)
            dp[(cur, flag)] = ans
            return ans

        return process(root, True)


    def rob3(self, root: Optional[TreeNode]) -> int:
        # 记忆化搜索
        dp = {}
        def process(cur):
            if not cur: return 0
            if cur in dp: return dp[cur]
            # 当前不偷
            ans = process(cur.left) + process(cur.right)
            # 当前偷
            ans2 = cur.val
            if cur.left:
                ans2 += process(cur.left.left) + process(cur.left.right)
            if cur.right:
                ans2 += process(cur.right.left) + process(cur.right.right)
            ans = max(ans, ans2)
            dp[cur] = ans
            return ans

        return process(root)